<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <script src="../static/js/jquery.js" charset="utf-8"></script>
    <style>
        .table_two {
            margin-left: 20px;
            border-collapse: collapse;
        }
        .table_two tr{
            height: 30px;
        }
        .table_two td{
            width: 30px;
        }
        .button {
            background-color: #4CAF50; /* Green */
            border: none;
            color: white;
            padding: 15px 32px;
            text-align: center;
            text-decoration: none;
            display: inline-block;
            font-size: 16px;
            margin: 10px;
        }
        .main_div{
            margin-top: 30px;
        }
        .bg-black{
            background-color: #807d7d; /* black */
            color: white;
        }
        
        .bg-red{
            background-color: #ee0e0e; /* black */
            color: white;
        }
        select {
            width: 100%;
            padding: 16px 20px;
            border: none;
            border-radius: 4px;
            background-color: #f1f1f1;
        }
    </style>
</head>
<body>
    <div>
        <select id="maze_size" name="maze_size" >
            </select>
    </div>
    <div style="width: 100%">
        <p id="context_area"></p>
        <p id="close_ext_len"></p>
        <p id="close_len"></p>
    </div>
    <div class="button" id="refresh">刷新</div>
    <div class="button" id="search">曼哈顿搜索</div>
    <div class="button" id="search_dia">对角搜索</div>
    <div id="main_div" class="main_div">
        <table id="first_node" class="table_two" border="1px">
        </table>
    </div>
    <script>
    maze_size_select()
    var __SIZE__=5
    var START_X=0,START_Y=0 //迷宫入口先默认设置为0
    var END_X=0,END_Y=0 //迷宫出口先默认设置为0
    var IS_PASS_OK=0  //是否存在解
    var ROAD=11   //路径
    var labys    //迷宫数组

    var heuri_type="MAN"

    function generator(){
        END_X=__SIZE__-1
        END_Y=__SIZE__-1

        var _td_node=[]
        var gen_node=[]
        for(var i=0;i<__SIZE__;i++){
            _td_node.push("<tr>")
            var _tr_arr=[]
            gen_node.push(_tr_arr)
            for(var j=0;j<__SIZE__;j++){
                var is_pass=Math.random()>0.625?1:0
                if(j==__SIZE__-1&&i==__SIZE__-1)is_pass=0
                if(j==0&&i==0)is_pass=0
                gen_node[i][j]=is_pass
                _td_node.push("<td class=\""+(is_pass==0?'bg-green':'bg-black')+"\">"+is_pass+"</td>")
            }
            _td_node.push("</tr>")
        }
        $("#first_node").append(_td_node.join(""))
        labys=gen_node
        return gen_node
    }
    $("#refresh").click(function(){
        $("#close_ext_len").html("")
        $("#close_len").html("")
        $("#first_node").html("")
        generator()
        
    })
    $("#search").click(function(){
        IS_PASS_OK=0
        var start_date = new Date(); //新建一个日期对象，默认现在的时间
        search()
        var end_date = new Date(); //新建一个日期对象，默认现在的时间
        var minus=end_date.getTime()-start_date.getTime()
        var str=IS_PASS_OK==1?" 迷宫有解 ":" 迷宫无解 "
	    $("#context_area").html(str+"曼哈顿估价执行耗时："+(minus/1000)+" s")
        
        
    })

    $("#search_dia").click(function(){
        heuri_type="DIA"
        IS_PASS_OK=0
        var start_date = new Date(); //新建一个日期对象，默认现在的时间
        search()
        var end_date = new Date(); //新建一个日期对象，默认现在的时间
        var minus=end_date.getTime()-start_date.getTime()
        var str=IS_PASS_OK==1?" 迷宫有解 ":" 迷宫无解 "
	    $("#context_area").append(" | "+str+"对角估价执行耗时："+(minus/1000)+" s")
        
        heuri_type="MAN"
    })
    function gs(i,j){
        return Math.abs(i - START_X) + Math.abs(j - START_Y)
    }

    function heuristic_dia(i,j){
        return (Math.pow(i - END_X,2) + Math.pow(j - END_Y,2))
    }
    function heuristic_man(i,j){
        return 10*(Math.abs(i - END_X) + Math.abs(j - END_Y))
    }
    function heuristic(i,j){
        if(heuri_type=="MAN"){
            return heuristic_man(i,j)
        }else{
            return heuristic_dia(i,j)
        }
    }


    
    function search(){
        ROAD=11
        var _labys=labys
        var open_arr=[]
        var start=[START_X,START_Y,0]
        open_arr.push(start)
        var close_arr=[]
        //close_arr.push(start)
        var close_ext_arr=[] //扩展结点
        //close_ext_arr.push(start)
        var path_arr=[]
        
        while(open_arr.length>0){
            var last_index=find_min_index(open_arr);
            var last_one=open_arr[last_index]
            var curr_row=last_one[0],curr_col=last_one[1]
            open_arr.splice(last_index,1)
            
            if(last_one[0]==END_X&&last_one[1]==END_Y){
                
                $("#close_ext_len").html("<p>扩展节点数为："+close_ext_arr.length+"</p>")
                $("#close_len").html("<p>生成节点数为："+(close_arr.length+1)+"</p>")
                open_arr=[]
                painting(_labys,path_arr)
                IS_PASS_OK=1
                break
            }else{
                //open_arr=[]
                var MIN_STEP=1000 //
                //向下探索
                if(curr_row+1<__SIZE__&&_labys[curr_row+1][curr_col]==0){
                    var cost=gs(curr_row+1,curr_col)+heuristic(curr_row+1,curr_col)
                    
                    if(!arrayHas(close_arr,[curr_row+1,curr_col,cost])){
                        open_arr.push([curr_row+1,curr_col,cost])
                    }
                }
                //向上探索
                if(curr_row-1>-1&&_labys[curr_row-1][curr_col]==0){
                    var cost=gs(curr_row-1,curr_col)+heuristic(curr_row-1,curr_col)
                    
                    if(!arrayHas(close_arr,[curr_row-1,curr_col,cost])){
                        open_arr.push([curr_row-1,curr_col,cost])
                    }
                }
                //向右探索
                if(curr_col+1<__SIZE__&&_labys[curr_row][curr_col+1]==0){
                    var cost=gs(curr_row,curr_col+1)+heuristic(curr_row,curr_col+1)
                    
                    if(!arrayHas(close_arr,[curr_row,curr_col+1,cost])){
                        open_arr.push([curr_row,curr_col+1,cost])
                    }
                }
                //向左探索
                if(curr_col-1>-1&&_labys[curr_row][curr_col-1]==0){
                    var cost=gs(curr_row,curr_col-1)+heuristic(curr_row,curr_col-1)
                    
                    if(!arrayHas(close_arr,[curr_row,curr_col-1,cost])){
                        open_arr.push([curr_row,curr_col-1,cost])
                    }
                }
                path_arr.push([curr_row,curr_col,ROAD])
                //_labys[curr_row][curr_col] = ROAD
                ROAD = ROAD + 1
                if(!arrayHas(close_arr,[curr_row,curr_col,last_one[2]])){
                    close_arr.push([curr_row,curr_col,last_one[2]])
                }
                
                for (const item in open_arr) {
                    if(!arrayHas(close_ext_arr,open_arr[item])){
                        close_ext_arr.push(open_arr[item])
                    }
                    
                }

                
                
            }
        }

        console.info(open_arr)

    }


    
    function find_min_index(arrs){
        
        var temp_min=9999999
        var index=0
        for(var i=0;i<arrs.length;i++){
            if(arrs[i][2]<temp_min){
                temp_min=arrs[i][2]
                index= i 
            }
        }
        return index

    }

    function painting(labys,path_arr){
        //$("#first_node").html("")
        var _td_node=[]
        var path_dict={}
        for (let i = 0; i < path_arr.length; i++) {
            var key=path_arr[i][0]+"_"+path_arr[i][1]
            path_dict[key]=path_arr[i][2]
        }

        for(var i=0;i<labys.length;i++){
            _td_node.push("<tr>")
            
            for(var j=0;j<labys[i].length;j++){
                var road_step=path_dict[i+"_"+j]
                var is_pass=labys[i][j]
                if(road_step!=undefined&&road_step!=null){
                    is_pass=road_step
                }
                
                if(is_pass==0){
                    _td_node.push("<td>"+is_pass+"</td>")
                }else if(is_pass==1){
                    _td_node.push("<td class=\"bg-black\"\">"+is_pass+"</td>")
                }else{
                    _td_node.push("<td class=\"bg-red\">"+is_pass+"</td>")
                }
            }
            _td_node.push("</tr>")
        }
        $("#first_node").html(_td_node.join(""))
    }


    function arrayHas(array, element) {  // 判断二维数组array中是否存在一维数组element
        for (var el of array) {
            if (el.length === element.length) {
            for (var index in el) {
                if (el[index] !== element[index]) {
                break;
                }
                if (index == (el.length - 1)) {    // 到最后一个元素都没有出现不相等，就说明这两个数组相等。
                return true;
                }
            }
            }
        }
        return false;
    }
    function maze_size_select(){
        for (let index = 5; index <= 64; index++) {
            $("#maze_size").append("<option value=\""+index+"\">"+index+"*"+index+"</option>")
        }
    }


    $(function(){

        $("#maze_size").change(function(){
            __SIZE__= $("#maze_size").val()
            $("#refresh").click()
        })

        $("#refresh").click()

    })
    
    </script>
</body>
</html>